{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Cutting Ribbons"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxLength"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #割绳子"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>ribbons</code> 和一个整数 <code>k</code>，数组每项 <code>ribbons[i]</code> 表示第 <code>i</code> 条绳子的长度。对于每条绳子，你可以将任意切割成一系列长度为<strong>正整数</strong>的部分，或者选择不进行切割。</p>\n",
    "\n",
    "<p>例如，如果给你一条长度为 <code>4</code> 的绳子，你可以：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>保持绳子的长度为 <code>4</code> 不变；</li>\n",
    "\t<li>切割成一条长度为 <code>3</code> 和一条长度为 <code>1</code> 的绳子；</li>\n",
    "\t<li>切割成两条长度为 <code>2</code> 的绳子；</li>\n",
    "\t<li>切割成一条长度为 <code>2</code> 和两条长度为 <code>1</code> 的绳子；</li>\n",
    "\t<li>切割成四条长度为 <code>1</code> 的绳子。</li>\n",
    "</ul>\n",
    "\n",
    "<p>你的任务是最终得到 <code>k</code> 条完全一样的绳子，他们的长度均为<strong>相同的正整数</strong>。如果绳子切割后有剩余，你可以直接舍弃掉多余的部分。</p>\n",
    "\n",
    "<p>对于这 <code>k</code> 根绳子，返回你能得到的绳子<strong>最大</strong>长度；如果你无法得到 <code>k</code> 根相同长度的绳子，返回 <code>0</code>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> ribbons = [9,7,5], k = 3\n",
    "<strong>输出:</strong> 5\n",
    "<strong>解释:</strong>\n",
    "- 把第一条绳子切成两部分，一条长度为 5，一条长度为 4；\n",
    "- 把第二条绳子切成两部分，一条长度为 5，一条长度为 2；\n",
    "- 第三条绳子不进行切割；\n",
    "现在，你得到了 3 条长度为 5 的绳子。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> ribbons = [7,5,9], k = 4\n",
    "<strong>输出:</strong> 4\n",
    "<strong>解释:</strong>\n",
    "- 把第一条绳子切成两部分，一条长度为 4，一条长度为 3；\n",
    "- 把第二条绳子切成两部分，一条长度为 4，一条长度为 1；\n",
    "- 把第二条绳子切成三部分，一条长度为 4，一条长度为 4，还有一条长度为 1；\n",
    "现在，你得到了 4 条长度为 4 的绳子。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre><strong>输入:</strong> ribbons = [5,7,9], k = 22\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong> 由于绳子长度需要为正整数，你无法得到 22 条长度相同的绳子。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= ribbons.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= ribbons[i] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [cutting-ribbons](https://leetcode.cn/problems/cutting-ribbons/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [cutting-ribbons](https://leetcode.cn/problems/cutting-ribbons/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[9,7,5]\\n3', '[7,5,9]\\n4', '[5,7,9]\\n22']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        '''\n",
    "        cut ribbons from 1 - max(ribbons) to count the how many pieces we will get\n",
    "        '''\n",
    "        l, r = 1, max(ribbons)\n",
    "        \n",
    "        while l <= r:\n",
    "            mid = (l+r)//2\n",
    "            pieces = self.cutPieces(ribbons, mid)\n",
    "            if pieces >= k:\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l-1\n",
    "    \n",
    "    def cutPieces(self, ribbons, length):\n",
    "        count = 0 \n",
    "        for ribbon in ribbons:\n",
    "            count += ribbon // length\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        s = sum(ribbons)\n",
    "        if k > s:\n",
    "            return 0\n",
    "        if k == s:\n",
    "            return 1\n",
    "        low, high = 1, max(ribbons)\n",
    "        ans = 1\n",
    "\n",
    "        def check(x):\n",
    "            res = 0\n",
    "            for i in ribbons:\n",
    "                res += i // x\n",
    "            return res >= k \n",
    "\n",
    "        while low <= high:\n",
    "            mid = (low + high) >> 1\n",
    "            if check(mid):\n",
    "                ans = mid \n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        def check(length):\n",
    "            sum=0\n",
    "            for ribbon in ribbons:\n",
    "                sum+=ribbon//length\n",
    "            return sum>=k\n",
    "        l,r=1,max(ribbons)\n",
    "        while l+1<r:\n",
    "            mid=(l+r)//2\n",
    "            if check(mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid\n",
    "        if check(r):\n",
    "            return r\n",
    "        if check(l):\n",
    "            return l\n",
    "        return 0\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "\n",
    "      \n",
    "        start, end = 1, max(ribbons)\n",
    "\n",
    "        if end < 1:\n",
    "            return 0\n",
    "\n",
    "        while start + 1 < end:\n",
    "            mid = (start + end) // 2\n",
    "            if self.getRes(ribbons, mid) >= k:\n",
    "                start = mid\n",
    "            else:\n",
    "                end = mid\n",
    "\n",
    "        if self.getRes(ribbons, end) >= k:\n",
    "            return end\n",
    "        if self.getRes(ribbons, start) >= k:\n",
    "            return start\n",
    "\n",
    "        return 0\n",
    "\n",
    "    def getRes(self, ribbons, len):\n",
    "        return sum(line // len for line in ribbons)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        def bis_find(self, ribbons, k, m):\n",
    "            if m == 0:\n",
    "                return True\n",
    "            sum = 0\n",
    "            for ribbon in ribbons:\n",
    "                sum += ribbon // m\n",
    "            return sum >= k\n",
    "\n",
    "        l = 0\n",
    "        r = 0\n",
    "        for ribbon in ribbons:\n",
    "            r = max(r, ribbon)\n",
    "        r = r * 2\n",
    "\n",
    "\n",
    "        while l <= r:\n",
    "            m = l + (r - l) // 2\n",
    "            if bis_find(self, ribbons, k, m):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        \n",
    "        return l if bis_find(self, ribbons, k, l) else l - 1\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        def bis_find(self, ribbons, k, m):\n",
    "            if m == 0:\n",
    "                return True\n",
    "            sum = 0\n",
    "            for ribbon in ribbons:\n",
    "                sum += int(ribbon / m)\n",
    "            return sum >= k\n",
    "\n",
    "        l = 0\n",
    "        r = 0\n",
    "        for ribbon in ribbons:\n",
    "            r = max(r, ribbon)\n",
    "        r = r * 2\n",
    "\n",
    "\n",
    "        while l <= r:\n",
    "            m = int(l + (r - l) / 2)\n",
    "            if bis_find(self, ribbons, k, m):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        \n",
    "        return l if bis_find(self, ribbons, k, l) else l - 1\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        def bis_find(self, ribbons, k, m):\n",
    "            if m == 0:\n",
    "                return True\n",
    "            sum = 0\n",
    "            for ribbon in ribbons:\n",
    "                sum += ribbon // m\n",
    "            return sum >= k\n",
    "\n",
    "        l = 0\n",
    "        r = 0\n",
    "        for ribbon in ribbons:\n",
    "            r = max(r, ribbon)\n",
    "        r = r * 2\n",
    "\n",
    "\n",
    "        while l <= r:\n",
    "            m = l + (r - l) // 2\n",
    "            if bis_find(self, ribbons, k, m):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        \n",
    "        return l - 1\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        start, end = 1, max(ribbons)\n",
    "        def is_possible(length):\n",
    "            count = 0\n",
    "            for num in ribbons:\n",
    "                count += num//length\n",
    "            return count >= k\n",
    "\n",
    "        while start + 1 < end:\n",
    "            mid = (start + end)//2\n",
    "            if is_possible(mid):\n",
    "                start = mid\n",
    "            else:\n",
    "                end = mid\n",
    "        if is_possible(end):\n",
    "            return end\n",
    "        elif is_possible(start):\n",
    "            return start\n",
    "        else:\n",
    "            return 0 # must have\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "\n",
    "        def check(m):\n",
    "            res = 0\n",
    "            for r in ribbons:\n",
    "                res += r//m \n",
    "                if res >= k:\n",
    "                    return True\n",
    "\n",
    "        sm = sum(ribbons)\n",
    "        l,r = 1, sm//k\n",
    "        while l <= r:\n",
    "            mid = (l+r)>>1\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        \n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        l, r = 0, max(ribbons) + 1\n",
    "        def count(val):\n",
    "            cnt = 0\n",
    "            for ribbon in ribbons:\n",
    "                cnt += ribbon // val\n",
    "            return cnt\n",
    "\n",
    "        while l + 1 < r:\n",
    "            m = (l + r) // 2\n",
    "            if count(m) >= k:\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        s = sum(ribbons)\n",
    "        if k > s:\n",
    "            return 0\n",
    "        if k == s:\n",
    "            return 1\n",
    "        low, high = 1, min(s // k, max(ribbons))\n",
    "        ans = 1\n",
    "\n",
    "        def check(x):\n",
    "            res = 0\n",
    "            for i in ribbons:\n",
    "                res += i // x\n",
    "            return res >= k \n",
    "\n",
    "        while low <= high:\n",
    "            mid = (low + high) >> 1\n",
    "            if check(mid):\n",
    "                ans = mid \n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        n = len(ribbons)\n",
    "        def check(mid):\n",
    "            s = sum(x // mid for x in ribbons)\n",
    "            return s >= k\n",
    "        l, r = 1, max(ribbons)\n",
    "        while l <= r:\n",
    "            mid = (l + r) // 2\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        if sum(ribbons) < k:\n",
    "            return 0\n",
    "\n",
    "        def bis_find(self, ribbons, k, m):\n",
    "            if m == 0:\n",
    "                return True\n",
    "            sum = 0\n",
    "            for ribbon in ribbons:\n",
    "                sum += ribbon // m\n",
    "            return sum >= k\n",
    "\n",
    "        l = 0\n",
    "        r = 0\n",
    "        for ribbon in ribbons:\n",
    "            r = max(r, ribbon)\n",
    "        r = r * 2\n",
    "\n",
    "\n",
    "        while l <= r:\n",
    "            m = l + (r - l) // 2\n",
    "            if bis_find(self, ribbons, k, m):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        \n",
    "        return l - 1\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        if sum(ribbons) < k:\n",
    "            return 0\n",
    "\n",
    "        def bis_find(self, ribbons, k, m):\n",
    "            if m == 0:\n",
    "                return True\n",
    "            sum = 0\n",
    "            for ribbon in ribbons:\n",
    "                sum += ribbon // m\n",
    "            return sum >= k\n",
    "\n",
    "        l = 0\n",
    "        r = 0\n",
    "        for ribbon in ribbons:\n",
    "            r = max(r, ribbon)\n",
    "        r = r * 2\n",
    "\n",
    "\n",
    "        while l <= r:\n",
    "            m = l + (r - l) // 2\n",
    "            if bis_find(self, ribbons, k, m):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        \n",
    "        return l - 1\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        def validate(length):\n",
    "            cnt = 0\n",
    "            for ribbon in ribbons:\n",
    "                cnt += ribbon // length\n",
    "            \n",
    "            if cnt >= k:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        l, r, sum_res = 0, 0, 0\n",
    "        for ribbon in ribbons:\n",
    "            sum_res += ribbon\n",
    "        r = sum_res // k\n",
    "\n",
    "        while l < r:\n",
    "            mid = l + (r - l + 1) // 2\n",
    "            if not validate(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid \n",
    "\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        if sum(ribbons) < k:\n",
    "            return 0\n",
    "\n",
    "        def check(length):\n",
    "            cnt = 0\n",
    "            for num in ribbons:\n",
    "                cnt += num // length\n",
    "            return cnt >= k\n",
    "\n",
    "        low = 1\n",
    "        high = max(ribbons)\n",
    "        res = 0\n",
    "        while low <= high :\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid+1\n",
    "                res = mid\n",
    "            else:\n",
    "                high = mid-1\n",
    "\n",
    "        return high\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        l=1\n",
    "        r=max(ribbons)+1\n",
    "        def check(mid):\n",
    "            ans=0\n",
    "            for r in ribbons:\n",
    "                ans+=r//mid\n",
    "            return ans>=k\n",
    "        while l<r:\n",
    "            mid=l+r+1>>1\n",
    "            if check(mid):\n",
    "                l=mid\n",
    "            else:\n",
    "                r=mid-1\n",
    "        return l if check(l) else 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "\n",
    "        def check(l):\n",
    "            total = 0\n",
    "            for i in range(len(ribbons)):\n",
    "                total += ribbons[i] // l \n",
    "                if total >= k:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        left, right = 1, max(ribbons) + 1\n",
    "        while left < right:\n",
    "            mid = (left + right) // 2\n",
    "            if check(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid\n",
    "        \n",
    "        if right == 1:\n",
    "            return 0\n",
    "        else:\n",
    "            return left - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        s = sum(ribbons)\n",
    "        if k > s:\n",
    "            return 0\n",
    "        if k == s:\n",
    "            return 1\n",
    "        low, high = 1, s // k\n",
    "        ans = 1\n",
    "\n",
    "        def check(x):\n",
    "            res = 0\n",
    "            for i in ribbons:\n",
    "                res += i // x\n",
    "            return res >= k \n",
    "\n",
    "        while low <= high:\n",
    "            mid = (low + high) >> 1\n",
    "            if check(mid):\n",
    "                ans = mid \n",
    "                low = mid + 1\n",
    "            else:\n",
    "                high = mid - 1\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        if sum(ribbons) < k:\n",
    "            return 0\n",
    "\n",
    "        def bis_find(self, ribbons, k, m):\n",
    "            if m == 0:\n",
    "                return True\n",
    "            sum = 0\n",
    "            for ribbon in ribbons:\n",
    "                sum += ribbon // m\n",
    "            return sum >= k\n",
    "\n",
    "        l = 0\n",
    "        r = 0\n",
    "        for ribbon in ribbons:\n",
    "            r = max(r, ribbon)\n",
    "        r = r * 2\n",
    "\n",
    "\n",
    "        while l <= r:\n",
    "            m = l + (r - l) // 2\n",
    "            if bis_find(self, ribbons, k, m):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        \n",
    "        return l - 1\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        left = 0\n",
    "        right = max(ribbons)\n",
    "\n",
    "        def check(curren_len):\n",
    "            chunks = 0\n",
    "            for ii in ribbons:\n",
    "                chunks += ii // curren_len\n",
    "            \n",
    "            return chunks >= k\n",
    "\n",
    "        while left < right:\n",
    "            mid = (left + right + 1) // 2\n",
    "            if not check(mid):\n",
    "                right = mid - 1\n",
    "            else:\n",
    "                left = mid\n",
    "        \n",
    "        return left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        def validate(length):\n",
    "            cnt = 0\n",
    "            for ribbon in ribbons:\n",
    "                cnt += ribbon // length\n",
    "            \n",
    "            if cnt >= k:\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        l, r, sum_res = 0, 0, 0\n",
    "        for ribbon in ribbons:\n",
    "            sum_res += ribbon\n",
    "        r = sum_res // k\n",
    "\n",
    "        while l < r:\n",
    "            mid = l + (r - l + 1) // 2\n",
    "            if not validate(mid):\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid \n",
    "\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        tt = sum(ribbons)\n",
    "        if tt <k: return 0\n",
    "        l, r = 0, tt // k\n",
    "\n",
    "        def checkOk(num):\n",
    "            cnt = 0\n",
    "            for l in ribbons:\n",
    "                cnt += l // num\n",
    "                if cnt >= k:\n",
    "                    return True\n",
    "\n",
    "            return False\n",
    "\n",
    "        while l < r:\n",
    "            mid = r - (r-l)//2\n",
    "            if checkOk(mid):\n",
    "                l = mid\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        start, end = 1, max(ribbons)\n",
    "        def is_possible(target):\n",
    "            count = 0\n",
    "            for num in ribbons:\n",
    "                count += num//target\n",
    "            return count >= k\n",
    "        while start + 1 < end:\n",
    "            mid = (start + end)//2\n",
    "            if is_possible(mid):\n",
    "                start = mid\n",
    "            else:\n",
    "                end = mid\n",
    "        if is_possible(end):\n",
    "            return end\n",
    "        elif is_possible(start):\n",
    "            return start\n",
    "        else:\n",
    "            return 0 # must have\n",
    " \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        ribbons.sort()\n",
    "\n",
    "        def binary(lf, ri):\n",
    "            while lf < ri:\n",
    "                mid = (lf + ri) // 2 + 1\n",
    "                res = 0\n",
    "                for i in range(len(ribbons)):\n",
    "                    res += ribbons[i] // mid\n",
    "                if res >= k:\n",
    "                    lf = mid\n",
    "                else:\n",
    "                    ri = mid - 1\n",
    "            return lf\n",
    "        res = binary(0, ribbons[-1])\n",
    "        return res if res else 0\n",
    "        \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        if sum(ribbons) < k:\n",
    "            return 0\n",
    "\n",
    "        def check(length):\n",
    "            cnt = 0\n",
    "            for num in ribbons:\n",
    "                cnt += num // length\n",
    "            return cnt >= k\n",
    "\n",
    "        low = 1\n",
    "        high = max(ribbons)\n",
    "        res = 0\n",
    "        while low <= high :\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid+1\n",
    "                res = mid\n",
    "            else:\n",
    "                high = mid-1\n",
    "\n",
    "        return low-1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        def bis_find(self, ribbons, k, m):\n",
    "            if m == 0:\n",
    "                return True\n",
    "            sum = 0\n",
    "            for ribbon in ribbons:\n",
    "                sum += ribbon // m\n",
    "            return sum >= k\n",
    "\n",
    "        l = 0\n",
    "        r = 0\n",
    "        for ribbon in ribbons:\n",
    "            r = max(r, ribbon)\n",
    "        r = r * 2\n",
    "\n",
    "\n",
    "        while l <= r:\n",
    "            m = l + (r - l) // 2\n",
    "            if bis_find(self, ribbons, k, m):\n",
    "                l = m + 1\n",
    "            else:\n",
    "                r = m - 1\n",
    "        \n",
    "        return l if bis_find(self, ribbons, k, l) else l - 1\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "不同长度的丝带，和k。我们要找出最大的整数长度，使得当你将这些丝带剪成这个长度时，你至少能得到 k 段丝带\n",
    "用二分找可能得最大长度 (1 - 最长的丝带中搜索)\n",
    "\n",
    "计算每条丝带能被剪成多少段指定长度的小段\n",
    "check给定长度 length，是否可以从所有ribbon中剪出k段\n",
    "\n",
    "如果 canCut(length) 返回 True，说明至少可以剪出 k 段，这时可以尝试更长的长度\n",
    "如果返回 False，则需要尝试更短的长度\n",
    "\"\"\"\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        def can_cut(length):\n",
    "            return sum(ribbon // length for ribbon in ribbons) >= k\n",
    "        \n",
    "        left, right = 1, max(ribbons)\n",
    "\n",
    "        # left <= right是为了遍历所有的ribbons\n",
    "        # 循环结束时，left 指向第一个无法满足条件的长度，而 right 指向最后一个能满足条件的长度。\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "\n",
    "            if can_cut(mid):\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        \n",
    "        return right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "\n",
    "        def check(m):\n",
    "            res = 0\n",
    "            for r in ribbons:\n",
    "                res += r//m \n",
    "                if res >= k:\n",
    "                    return True\n",
    "            return False\n",
    "\n",
    "        sm = sum(ribbons)\n",
    "        l,r = 1, sm//k\n",
    "        while l <= r:\n",
    "            mid = (l+r)>>1\n",
    "            if check(mid):\n",
    "                l = mid + 1\n",
    "            else:\n",
    "                r = mid - 1\n",
    "        \n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        if sum(ribbons) < k:\n",
    "            return 0\n",
    "        l = 1\n",
    "        r = max(ribbons)\n",
    "\n",
    "        def good(x):\n",
    "            res = 0\n",
    "            for ri in ribbons:\n",
    "                res += ri//x\n",
    "            return res >= k\n",
    "\n",
    "        while l + 1< r:\n",
    "            m = (l + r)//2\n",
    "            if good(m):\n",
    "                l = m\n",
    "            else:\n",
    "                r = m\n",
    "        \n",
    "        return r if good(r) else l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        start, end = 1, max(ribbons)\n",
    "        def is_possible(target):\n",
    "            count = 0\n",
    "            for num in ribbons:\n",
    "                count += num//target\n",
    "            return count >= k\n",
    "        while start + 1 < end:\n",
    "            mid = (start + end)//2\n",
    "            if is_possible(mid):\n",
    "                start = mid\n",
    "            else:\n",
    "                end = mid\n",
    "        if is_possible(end):\n",
    "            return end\n",
    "        elif is_possible(start):\n",
    "            return start\n",
    "        else:\n",
    "            return 0 # must have\n",
    " \n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        # 切割绳子函数，返回对于给定长度 x 可以得到的绳子数量\n",
    "        def cut(x: int) -> int:\n",
    "            count = 0\n",
    "            for ribbon in ribbons:\n",
    "                count += ribbon // x\n",
    "            return count\n",
    "\n",
    "        # 二分搜索\n",
    "        left, right, ans = 1, max(ribbons), 0\n",
    "        while left <= right:\n",
    "            mid = (left + right) // 2\n",
    "            if cut(mid) >= k:\n",
    "                ans = mid\n",
    "                left = mid + 1\n",
    "            else:\n",
    "                right = mid - 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        if sum(ribbons) < k:\n",
    "            return 0\n",
    "\n",
    "        def check(length):\n",
    "            cnt = 0\n",
    "            for num in ribbons:\n",
    "                cnt += num // length\n",
    "            return cnt >= k\n",
    "\n",
    "        low = 1\n",
    "        high = max(ribbons)\n",
    "        res = 0\n",
    "        while low <= high :\n",
    "            mid = low + (high - low) // 2\n",
    "            if check(mid):\n",
    "                low = mid+1\n",
    "                res = mid\n",
    "            else:\n",
    "                high = mid-1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        n = len(ribbons)\n",
    "        def getRibbonAmount(length):\n",
    "            count = 0\n",
    "            for ribbon in ribbons:\n",
    "                count += ribbon // length\n",
    "            return count\n",
    "        \n",
    "        l, r = 1, max(ribbons) + 1\n",
    "        while l < r:\n",
    "            mid = (l+r) // 2\n",
    "            count = getRibbonAmount(mid)\n",
    "            if count <= k - 1:\n",
    "                r = mid \n",
    "            else:\n",
    "                l = mid + 1\n",
    "        \n",
    "        print(getRibbonAmount(l), getRibbonAmount(l-1) if l > 1 else 0)\n",
    "        return l - 1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxLength(self, ribbons: List[int], k: int) -> int:\n",
    "        \n",
    "        def checkLen(l, k):\n",
    "            cnt = 0\n",
    "            for r in ribbons:\n",
    "                cnt += r //l\n",
    "            if cnt < k:\n",
    "                return False\n",
    "            else:\n",
    "                return True\n",
    "        \n",
    "        sum_rib = sum(ribbons)\n",
    "        lb, ub = 0, sum_rib//k\n",
    "\n",
    "        def biSearch(lb, ub, k):\n",
    "            while lb != ub:\n",
    "                mid = (lb + ub +1) //2\n",
    "                if checkLen(mid, k):\n",
    "                    lb = mid\n",
    "                else:\n",
    "                    ub = mid-1\n",
    "            return lb\n",
    "\n",
    "        return biSearch(lb, ub, k)\n",
    "        \n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
